import java.util.*;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025-02-12
 */
public class leetcode_239 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow3(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));

    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k && j < nums.length; j++) {
                max = Math.max(max, nums[j]);
            }
            list.add(max);
        }
        //list转int[]方法
        return list.stream().mapToInt(Integer::intValue).toArray();
    }


    //用堆 大根堆
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) {
            heap.add(nums[i]);
        }
        list.add(heap.peek());
        for (int i = 0; i < nums.length - k; i++) {
            heap.remove(nums[i]);
            heap.add(nums[i + k]);
            list.add(heap.peek());
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int n = nums.length; // 数组的长度
        int[] result = new int[n - k + 1]; // 结果数组，用于存储每个滑动窗口的最大值
        Deque<Integer> deque = new LinkedList<>(); // 双端队列，用来存储滑动窗口中的元素索引  deque(double point queue)

        // 遍历整个数组
        for (int i = 0; i < n; i++) {
            // 1. 如果队列中第一个元素不在当前窗口范围内（即索引小于 i - k + 1），移除队列头部元素
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst(); // 移除队列头部元素
            }

            // 2. 从队列尾部移除所有小于当前元素 nums[i] 的元素
            //    这是因为这些元素将永远不再成为当前窗口的最大值
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast(); // 移除队列尾部小于当前元素的索引
            }

            // 3. 将当前元素的索引加入队列尾部
            deque.offerLast(i);

            // 4. 如果当前索引 i >= k - 1，表示当前窗口已经完整，开始记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()]; // 队列头部的元素是当前窗口的最大值
            }
        }

        return result; // 返回结果数组，包含每个窗口的最大值
    }


    public static int[] maxSlidingWindow3(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int n = nums.length; // 数组的长度
        int[] res = new int[nums.length - k + 1];
        //这个deque 是记录i 不是记录值
        Deque<Integer> deque = new LinkedList<>();

        //如果是窗口   可以用最后的指针遍历 省下初始化的操作  小技巧
        for (int i = 0; i < nums.length; i++) {
            if(!deque.isEmpty()&&deque.peekFirst()<i-k+1){
                //删掉窗口之外的
                deque.pollFirst();
            }
            while(!deque.isEmpty()&&nums[i]>nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.addLast(i);
            //这一步 是为了让初始化完成  初始化完成后 就是移动一次 写一次 得到窗口最大值
            if(i>=k-1){
                res[i-k+1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}
